home *** CD-ROM | disk | FTP | other *** search
/ Aminet 28 / Aminet 28 (1998)(GTI - Schatztruhe)[!][Dec 1998].iso / Aminet / dev / c / qtools0.2-src.lha / src / libqbuild / portals.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-07-15  |  15.9 KB  |  603 lines
  1. #define    LIBQBUILD_CORE
  2. #include "../include/libqbuild.h"
  3.  
  4. struct node outside_node;                    /* 76                                          // portals outside the world face this */
  5.  
  6. FILE *pf;                            /* 4 */
  7. int num_visportals;                        /* 4 */
  8. int num_visleafs;                        /* 4                                           // leafs the player can be in */
  9. struct visportal *portals;
  10. struct visleaf **leafs;
  11.  
  12. /*============================================================================= */
  13.  
  14. /*
  15.  * =============
  16.  * AddPortalToNodes
  17.  * =============
  18.  */
  19. void AddPortalToNodes(register struct portal *p, register struct node *front, register struct node *back)
  20. {
  21.   if (p->nodes[0] || p->nodes[1])
  22.     Error("AddPortalToNode: allready included");
  23.  
  24.   p->nodes[0] = front;
  25.   p->next[0] = front->portals;
  26.   front->portals = p;
  27.  
  28.   p->nodes[1] = back;
  29.   p->next[1] = back->portals;
  30.   back->portals = p;
  31. }
  32.  
  33. /*
  34.  * =============
  35.  * RemovePortalFromNode
  36.  * =============
  37.  */
  38. void RemovePortalFromNode(register struct portal *portal, register struct node *l)
  39. {
  40.   struct portal **pp, *t;
  41.  
  42.   /* remove reference to the current portal */
  43.   pp = &l->portals;
  44.   while (1) {
  45.     t = *pp;
  46.     if (!t)
  47.       Error("RemovePortalFromNode: portal not in leaf");
  48.  
  49.     if (t == portal)
  50.       break;
  51.  
  52.     if (t->nodes[0] == l)
  53.       pp = &t->next[0];
  54.     else if (t->nodes[1] == l)
  55.       pp = &t->next[1];
  56.     else
  57.       Error("RemovePortalFromNode: portal not bounding leaf");
  58.   }
  59.  
  60.   if (portal->nodes[0] == l) {
  61.     *pp = portal->next[0];
  62.     portal->nodes[0] = NULL;
  63.   }
  64.   else if (portal->nodes[1] == l) {
  65.     *pp = portal->next[1];
  66.     portal->nodes[1] = NULL;
  67.   }
  68. }
  69.  
  70. /*============================================================================ */
  71.  
  72. void PrintPortal(register struct portal *p)
  73. {
  74.   int i;
  75.   struct winding *w;
  76.  
  77.   w = p->winding;
  78.   for (i = 0; i < w->numpoints; i++)
  79.     mprintf("( %g %g %g )\n", w->points[i][0], w->points[i][1], w->points[i][2]);
  80. }
  81.  
  82. /*
  83.  * ================
  84.  * MakeHeadnodePortals
  85.  * 
  86.  * The created portals will face the global outside_node
  87.  * ================
  88.  */
  89. void MakeHeadnodePortals(__memBase, register struct node *node)
  90. {
  91.   vec3_t bounds[2];
  92.   short int i, j, n;
  93.   struct portal *p, *portals[6];
  94.   struct plane bplanes[6], *pl;
  95.   int side;
  96.  
  97.   Draw_ClearWindow();
  98.  
  99.   /* pad with some space so there will never be null volume leafs */
  100.   for (i = 0; i < 3; i++) {
  101.     bounds[0][i] = brushset->mins[i] - SIDESPACE;
  102.     bounds[1][i] = brushset->maxs[i] + SIDESPACE;
  103.   }
  104.  
  105.   outside_node.contents = CONTENTS_SOLID;
  106.   outside_node.portals = NULL;
  107.  
  108.   for (i = 0; i < 3; i++)
  109.     for (j = 0; j < 2; j++) {
  110.       n = j * 3 + i;
  111.  
  112.       p = AllocPortal();
  113.       portals[n] = p;
  114.  
  115.       pl = &bplanes[n];
  116.       __bzero(pl, sizeof(*pl));
  117.       if (j) {
  118.     pl->normal[i] = -1;
  119.     pl->dist = -bounds[j][i];
  120.       }
  121.       else {
  122.     pl->normal[i] = 1;
  123.     pl->dist = bounds[j][i];
  124.       }
  125.       p->planenum = FindPlane(bspMem, pl, &side);
  126.  
  127.       p->winding = BaseWindingForPlane(pl);
  128.       if (side)
  129.     AddPortalToNodes(p, &outside_node, node);
  130.       else
  131.     AddPortalToNodes(p, node, &outside_node);
  132.     }
  133.  
  134.   /* clip the basewindings by all the other planes */
  135.   for (i = 0; i < 6; i++) {
  136.     for (j = 0; j < 6; j++) {
  137.       if (j == i)
  138.     continue;
  139.       portals[i]->winding = ClipWinding(portals[i]->winding, &bplanes[j], TRUE);
  140.     }
  141.   }
  142. }
  143.  
  144. /*============================================================================ */
  145.  
  146. void CheckLeafPortalConsistancy(__memBase, register struct node *node)
  147. {
  148.   int side, side2;
  149.   struct portal *p, *p2;
  150.   struct plane plane, plane2;
  151.   int i;
  152.   struct winding *w;
  153.   float dist;
  154.  
  155.   side = side2 = 0;                        /* quiet compiler warning */
  156.  
  157.   for (p = node->portals; p; p = p->next[side]) {
  158.     if (p->nodes[0] == node)
  159.       side = 0;
  160.     else if (p->nodes[1] == node)
  161.       side = 1;
  162.     else
  163.       Error("CutNodePortals_r: mislinked portal");
  164.     CheckWindingInNode(p->winding, node);
  165.     CheckWindingArea(p->winding);
  166.  
  167.     /* check that the side orders are correct */
  168. #ifdef EXHAUSIVE_CHECK
  169.     if (p->planenum >= bspMem->numbrushplanes || p->planenum < 0)
  170.       Error("looking for nonexisting plane %d\n", p->planenum);
  171. #endif
  172.     plane = bspMem->brushplanes[p->planenum];
  173.     PlaneFromWinding(p->winding, &plane2);
  174.  
  175.     for (p2 = node->portals; p2; p2 = p2->next[side2]) {
  176.       if (p2->nodes[0] == node)
  177.     side2 = 0;
  178.       else if (p2->nodes[1] == node)
  179.     side2 = 1;
  180.       else
  181.     Error("CutNodePortals_r: mislinked portal");
  182.       w = p2->winding;
  183.       for (i = 0; i < w->numpoints; i++) {
  184.     dist = DotProduct(w->points[i], plane.normal) - plane.dist;
  185.     if ((side == 0 && dist < -1) || (side == 1 && dist > 1)) {
  186.       eprintf("portal siding direction is wrong\n");
  187.       return;
  188.     }
  189.       }
  190.     }
  191.   }
  192. }
  193.  
  194. /*
  195.  * ================
  196.  * CutNodePortals_r
  197.  * 
  198.  * ================
  199.  */
  200. void CutNodePortals_r(__memBase, register struct node *node)
  201. {
  202.   struct plane *plane, clipplane;
  203.   struct node *f, *b, *other_node;
  204.   struct portal *p, *new_portal, *next_portal;
  205.   struct winding *w, *frontwinding, *backwinding;
  206.   int side;
  207.  
  208.   /* CheckLeafPortalConsistancy (node); */
  209.  
  210.   /* seperate the portals on node into it's children */
  211.   if (node->contents)
  212.     return;                            /* at a leaf, no more dividing */
  213.  
  214. #ifdef EXHAUSIVE_CHECK
  215.   if (node->planenum >= bspMem->numbrushplanes || node->planenum < 0)
  216.     Error("looking for nonexisting plane %d\n", node->planenum);
  217. #endif
  218.   plane = &bspMem->brushplanes[node->planenum];
  219.  
  220.   f = node->children[0];
  221.   b = node->children[1];
  222.  
  223.   /*
  224.    * create the new portal by taking the full plane winding for the cutting plane
  225.    * and clipping it by all of the planes from the other portals
  226.    */
  227.   new_portal = AllocPortal();
  228.   new_portal->planenum = node->planenum;
  229.  
  230.   w = BaseWindingForPlane(&bspMem->brushplanes[node->planenum]);
  231.   side = 0;                            /* shut up compiler warning */
  232.  
  233.   for (p = node->portals; p; p = p->next[side]) {
  234.     clipplane = bspMem->brushplanes[p->planenum];
  235.     if (p->nodes[0] == node)
  236.       side = 0;
  237.     else if (p->nodes[1] == node) {
  238.       clipplane.dist = -clipplane.dist;
  239.       VectorNegate(clipplane.normal);
  240.       side = 1;
  241.     }
  242.     else
  243.       Error("CutNodePortals_r: mislinked portal");
  244.  
  245.     w = ClipWinding(w, &clipplane, TRUE);
  246.     if (!w) {
  247.       eprintf("CutNodePortals_r: new portal was clipped away\n");
  248.       break;
  249.     }
  250.   }
  251.  
  252.   if (w) {
  253.     /* if the plane was not clipped on all sides, there was an error */
  254.     new_portal->winding = w;
  255.     AddPortalToNodes(new_portal, f, b);
  256.   }
  257.  
  258.   /* partition the portals */
  259.   for (p = node->portals; p; p = next_portal) {
  260.     if (p->nodes[0] == node)
  261.       side = 0;
  262.     else if (p->nodes[1] == node)
  263.       side = 1;
  264.     else
  265.       Error("CutNodePortals_r: mislinked portal");
  266.     next_portal = p->next[side];
  267.  
  268.     other_node = p->nodes[!side];
  269.     RemovePortalFromNode(p, p->nodes[0]);
  270.     RemovePortalFromNode(p, p->nodes[1]);
  271.  
  272.     /* cut the portal into two portals, one on each side of the cut plane */
  273.     DivideWinding(p->winding, plane, &frontwinding, &backwinding);
  274.  
  275.     if (!frontwinding) {
  276.       if (side == 0)
  277.     AddPortalToNodes(p, b, other_node);
  278.       else
  279.     AddPortalToNodes(p, other_node, b);
  280.       continue;
  281.     }
  282.     if (!backwinding) {
  283.       if (side == 0)
  284.     AddPortalToNodes(p, f, other_node);
  285.       else
  286.     AddPortalToNodes(p, other_node, f);
  287.       continue;
  288.     }
  289.  
  290.     /* the winding is split */
  291.     new_portal = AllocPortal();
  292.     *new_portal = *p;
  293.     new_portal->winding = backwinding;
  294.     FreeWinding(p->winding);
  295.     p->winding = frontwinding;
  296.  
  297.     if (side == 0) {
  298.       AddPortalToNodes(p, f, other_node);
  299.       AddPortalToNodes(new_portal, b, other_node);
  300.     }
  301.     else {
  302.       AddPortalToNodes(p, other_node, f);
  303.       AddPortalToNodes(new_portal, other_node, b);
  304.     }
  305.   }
  306.  
  307.   DrawLeaf(f, 1);
  308.   DrawLeaf(b, 2);
  309.  
  310.   CutNodePortals_r(bspMem, f);
  311.   CutNodePortals_r(bspMem, b);
  312.  
  313. }
  314.  
  315. /*
  316.  * ==================
  317.  * PortalizeWorld
  318.  * 
  319.  * Builds the exact polyhedrons for the nodes and leafs
  320.  * ==================
  321.  */
  322. void PortalizeWorld(__memBase, struct node *headnode)
  323. {
  324.   mprintf("----- Portalize ---------\n");
  325.  
  326.   MakeHeadnodePortals(bspMem, headnode);
  327.   CutNodePortals_r(bspMem, headnode);
  328. }
  329.  
  330. /*
  331.  * ==================
  332.  * FreeAllPortals
  333.  * 
  334.  * ==================
  335.  */
  336. void FreeAllPortals(struct node *node)
  337. {
  338.   struct portal *p, *nextp;
  339.  
  340.   if (!node->contents) {
  341.     FreeAllPortals(node->children[0]);
  342.     FreeAllPortals(node->children[1]);
  343.   }
  344.  
  345.   for (p = node->portals; p; p = nextp) {
  346.     if (p->nodes[0] == node)
  347.       nextp = p->next[0];
  348.     else
  349.       nextp = p->next[1];
  350.     RemovePortalFromNode(p, p->nodes[0]);
  351.     RemovePortalFromNode(p, p->nodes[1]);
  352.     FreeWinding(p->winding);
  353.     FreePortal(p);
  354.   }
  355. }
  356.  
  357. /*
  358.  * ==============================================================================
  359.  * 
  360.  * PORTAL FILE GENERATION
  361.  * 
  362.  * ==============================================================================
  363.  */
  364.  
  365. void WritePortalFile_r(__memBase, register struct node *node)
  366. {
  367.   int i;
  368.   struct portal *p;
  369.   struct winding *w;
  370.   struct plane *pl, plane2;
  371.  
  372.   if (!node->contents) {
  373.     WritePortalFile_r(bspMem, node->children[0]);
  374.     WritePortalFile_r(bspMem, node->children[1]);
  375.     return;
  376.   }
  377.  
  378.   if (node->contents == CONTENTS_SOLID)
  379.     return;
  380.  
  381.   for (p = node->portals; p;) {
  382.     w = p->winding;
  383.     if (w && p->nodes[0] == node) {
  384.       if (((bspMem->bspOptions & QBSP_WATERVIS) &&
  385.        ((p->nodes[0]->contents == CONTENTS_WATER && p->nodes[1]->contents == CONTENTS_EMPTY) ||
  386.         (p->nodes[0]->contents == CONTENTS_EMPTY && p->nodes[1]->contents == CONTENTS_WATER)))
  387.       || ((bspMem->bspOptions & QBSP_SLIMEVIS) &&
  388.           ((p->nodes[0]->contents == CONTENTS_SLIME && p->nodes[1]->contents == CONTENTS_EMPTY) ||
  389.            (p->nodes[0]->contents == CONTENTS_EMPTY && p->nodes[1]->contents == CONTENTS_SLIME)))
  390.       || ((bspMem->bspOptions & QBSP_WATERVIS) && (bspMem->bspOptions & QBSP_SLIMEVIS) &&
  391.           ((p->nodes[0]->contents == CONTENTS_WATER && p->nodes[1]->contents == CONTENTS_SLIME) ||
  392.            (p->nodes[0]->contents == CONTENTS_SLIME && p->nodes[1]->contents == CONTENTS_WATER)))
  393.       || (p->nodes[0]->contents == p->nodes[1]->contents)) {
  394.     /*
  395.      * write out to the file
  396.      *
  397.      * sometimes planes get turned around when they are very near
  398.      * the changeover point between different axis.  interpret the
  399.      * plane the same way vis will, and flip the side orders if needed
  400.      */
  401. #ifdef EXHAUSIVE_CHECK
  402.     if (p->planenum >= bspMem->numbrushplanes || p->planenum < 0)
  403.       Error("looking for nonexisting plane %d\n", p->planenum);
  404. #endif
  405.     pl = &bspMem->brushplanes[p->planenum];
  406.     PlaneFromWinding(w, &plane2);
  407.  
  408.     if (DotProduct(pl->normal, plane2.normal) < 0.99)    /* backwards... */
  409.       fprintf(pf, "%i %i %i ", w->numpoints, p->nodes[1]->visleafnum, p->nodes[0]->visleafnum);
  410.     else
  411.       fprintf(pf, "%i %i %i ", w->numpoints, p->nodes[0]->visleafnum, p->nodes[1]->visleafnum);
  412.  
  413.     for (i = 0; i < w->numpoints; i++)
  414.       fprintf(pf, "( %g %g %g ) ", w->points[i][0], w->points[i][1], w->points[i][2]);
  415.     fprintf(pf, "\n");
  416.       }
  417.     }
  418.  
  419.     if (p->nodes[0] == node)
  420.       p = p->next[0];
  421.     else
  422.       p = p->next[1];
  423.   }
  424.  
  425. }
  426.  
  427. /*
  428.  * ================
  429.  * NumberLeafs_r
  430.  * ================
  431.  */
  432. void NumberLeafs_r(__memBase, register struct node *node)
  433. {
  434.   struct portal *p;
  435.  
  436.   if (!node->contents) {                    /* decision node */
  437.     node->visleafnum = -99;
  438.     NumberLeafs_r(bspMem, node->children[0]);
  439.     NumberLeafs_r(bspMem, node->children[1]);
  440.     return;
  441.   }
  442.  
  443.   Draw_ClearWindow();
  444.   DrawLeaf(node, 1);
  445.  
  446.   if (node->contents == CONTENTS_SOLID) {            /* solid block, viewpoint never inside */
  447.     node->visleafnum = -1;
  448.     return;
  449.   }
  450.  
  451.   node->visleafnum = num_visleafs++;
  452.  
  453.   for (p = node->portals; p;) {
  454.     if (p->nodes[0] == node) {                    /* only write out from first leaf */
  455.       if (((bspMem->bspOptions & QBSP_WATERVIS) &&
  456.        ((p->nodes[0]->contents == CONTENTS_WATER && p->nodes[1]->contents == CONTENTS_EMPTY) ||
  457.         (p->nodes[0]->contents == CONTENTS_EMPTY && p->nodes[1]->contents == CONTENTS_WATER)))
  458.       || ((bspMem->bspOptions & QBSP_SLIMEVIS) &&
  459.           ((p->nodes[0]->contents == CONTENTS_SLIME && p->nodes[1]->contents == CONTENTS_EMPTY) ||
  460.            (p->nodes[0]->contents == CONTENTS_EMPTY && p->nodes[1]->contents == CONTENTS_SLIME)))
  461.       || ((bspMem->bspOptions & QBSP_WATERVIS) && (bspMem->bspOptions & QBSP_SLIMEVIS) &&
  462.           ((p->nodes[0]->contents == CONTENTS_WATER && p->nodes[1]->contents == CONTENTS_SLIME) ||
  463.            (p->nodes[0]->contents == CONTENTS_SLIME && p->nodes[1]->contents == CONTENTS_WATER)))
  464.       || (p->nodes[0]->contents == p->nodes[1]->contents)) {
  465.     num_visportals++;
  466.       }
  467.       p = p->next[0];
  468.     }
  469.     else
  470.       p = p->next[1];
  471.   }
  472. }
  473.  
  474. /*
  475.  * ================
  476.  * WritePortalfile
  477.  * ================
  478.  */
  479. void WritePortalfile(__memBase, struct node *headnode, char *portfilename)
  480. {
  481.   /* set the visleafnum field in every leaf and count the total number of portals */
  482.   num_visleafs = 0;
  483.   num_visportals = 0;
  484.   NumberLeafs_r(bspMem, headnode);
  485.  
  486.   /* write the file */
  487.   mprintf("    - writing %s\n", portfilename);
  488.   pf = __fopen(portfilename, "w");
  489.   if (!pf)
  490.     Error(failed_fileopen, portfilename);
  491.  
  492.   fprintf(pf, "%s\n", PORTALFILE);
  493.   fprintf(pf, "%i\n", num_visleafs);
  494.   fprintf(pf, "%i\n", num_visportals);
  495.  
  496.   WritePortalFile_r(bspMem, headnode);
  497.  
  498.   __fclose(pf);
  499. }
  500.  
  501. /*
  502.  * ============
  503.  * LoadPortals
  504.  * ============
  505.  */
  506. void LoadPortals(char *prtBuf)
  507. {
  508.   int i, j;
  509.   int read;
  510.   struct visportal *p;
  511.   struct visleaf *l;
  512.   char magic[80];
  513.   int numpoints;
  514.   struct winding *w;
  515.   int leafnums[2];
  516.   struct plane plane;
  517.  
  518.   mprintf("----- LoadPortals -------\n");
  519.  
  520.   if (sscanf(prtBuf, "%79s\n%i\n%i\n%n", magic, &num_visleafs, &num_visportals, &read) != 3)
  521.     Error("LoadPortals: failed to read header");
  522.   prtBuf += read;
  523.   if (strcmp(magic, PORTALFILE))
  524.     Error("LoadPortals: not a portal file");
  525.  
  526.   /* each file portal is split into two memory portals */
  527.   if (!(portals = (struct visportal *)tmalloc(2 * num_visportals * sizeof(struct visportal))))
  528.       Error(failed_memoryunsize, "visportal");
  529.  
  530.   /*leafs = (struct visleaf *)tmalloc(num_visleafs * sizeof(struct visleaf)); */
  531.   if (!(leafs = (struct visleaf **)tmalloc(num_visleafs * sizeof(struct visleaf *))))
  532.       Error(failed_memoryunsize, "visleaf");
  533.  
  534.   for (i = 0, p = portals; i < num_visportals; i++) {
  535.     if (sscanf(prtBuf, "%i %i %i %n", &numpoints, &leafnums[0], &leafnums[1], &read) != 3)
  536.       Error("LoadPortals: reading portal %i\n", i);
  537.     if (numpoints > MAX_POINTS_ON_WINDING)
  538.       Error("LoadPortals: portal %i has too many points\n", i);
  539.     if ((unsigned)leafnums[0] > num_visleafs || (unsigned)leafnums[1] > num_visleafs)
  540.       Error("LoadPortals: reading portal %i\n", i);
  541.     prtBuf += read;
  542.  
  543.     w = p->winding = NewWinding(numpoints);
  544.     w->original = TRUE;
  545.     w->numpoints = numpoints;
  546.  
  547.     for (j = 0; j < numpoints; j++) {
  548.       int k;
  549.  
  550.       /* scanf into double, then assign to vec_t */
  551.       if ((k = sscanf(prtBuf, "( %g %g %g ) %n", &w->points[j][0], &w->points[j][1], &w->points[j][2], &read)) != 3)
  552.     Error("LoadPortals: reading portal %i (%i elements)\n", i, k);
  553.       prtBuf += read;
  554.     }
  555.     sscanf(prtBuf, "\n%n", &read);
  556.     prtBuf += read;
  557.  
  558.     /* calc plane */
  559.     PlaneFromWinding(w, &plane);
  560.  
  561.     /* create forward portal */
  562.     /*l = &leafs[leafnums[0]]; */
  563.     if (!(l = leafs[leafnums[0]]))
  564.       l = leafs[leafnums[0]] = AllocLeaf(MAX_PORTALS_ON_LEAF);
  565.     else if (l->numportals == MAX_PORTALS_ON_LEAF)
  566.       Error("Leaf with too many portals");
  567.     l->portals[l->numportals] = p;
  568.     l->numportals++;
  569.  
  570.     p->winding = w;
  571.     VectorNegateTo(plane.normal, p->plane.normal);
  572.     p->plane.dist = -plane.dist;
  573.     p->leaf = leafnums[1];
  574.     p++;
  575.  
  576.     /* create backwards portal */
  577.     /*l = &leafs[leafnums[1]]; */
  578.     if (!(l = leafs[leafnums[1]]))
  579.       l = leafs[leafnums[1]] = AllocLeaf(MAX_PORTALS_ON_LEAF);
  580.     else if (l->numportals == MAX_PORTALS_ON_LEAF)
  581.       Error("Leaf with too many portals");
  582.     l->portals[l->numportals] = p;
  583.     l->numportals++;
  584.  
  585.     p->winding = w;
  586.     p->plane = plane;
  587.     p->leaf = leafnums[0];
  588.     p++;
  589.  
  590.     mprogress(num_visportals, i + 1);
  591.   }
  592.  
  593.   mprintf("%5i num_visportals\n", num_visportals);
  594.   mprintf("%5i num_visleafs\n", num_visleafs);
  595.  
  596.   for (i = 0; i < num_visleafs; i++) {
  597.     if (leafs[i])
  598.       RecalcLeaf(leafs[i]);
  599.     else
  600.       leafs[i] = AllocLeaf(MAX_PORTALS_ON_LEAF);
  601.   }
  602. }
  603.